/*
 * =====================================================================================
 *
 *       Filename:  SortProblem.h
 *
 *    Description:  排序算法相关问题
 *
 *        Version:  1.0
 *        Created:  2011-10-28 9:16:00
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  YOUR NAME
 *        Company:
 *
 * =====================================================================================
 */
#ifndef _SortProblem_H_
#define _SortProblem_H_


#include <vector>
#include <stack>
#include <string>
#include <limits>
#include <algorithm>

#include "Random.h"

//生成随机顺序的数组，可能存在重复元素
template <class Comparable>
void genRandVector(std::vector<Comparable> &A, int size)
{
    srand((int)time(0));
    A.resize(size);

    for(int i = 0; i < size; ++i) {
        A[i] = Comparable(averageRandom<Comparable>(-size, size));
    }
}

//生成随机顺序的数组，所有数值为正数，可能存在重复元素，
template <class Comparable>
void genPositiveRandVector(std::vector<Comparable> &A, int size)
{
    srand((int)time(0));
    A.resize(size);

    for(int i = 0; i < size; ++i) {
        A[i] = Comparable(abs(averageRandom<Comparable>(-size, size)));
    }
}

//判断数组是否有序
template <class Comparable>
bool isVectorOrdered(const std::vector<Comparable> &A)
{
    if (A.empty()) {
        return true;
    }

    for (int i = 0; i < (int)A.size() - 1; ++i) {
        if (A[i] > A[i + 1]) {
            return false;
        }
    }

    return true;
}

template <class Comparable>
void compSwap(Comparable &x, Comparable &y)
{
    if (x > y) {
        std::swap(x, y);
    }
}

//选择排序，运行时间O(n^2)，非稳定性算法
//(n^2/2)次比较，(n)次交换
template <class Comparable>
void selectSort(std::vector<Comparable> &A, int l, int r)
{
    for (int i = l; i < r; ++i) {
        int min = i;

        for (int j = i + 1; j <= r; ++j) {
            if (A[j] < A[min]) {
                min = j;
            }
        }

        std::swap(A[i], A[min]);
    }
}

//非适应性插入排序，运行时间O(n^2)，稳定性算法
//平均情况(n^2/4)次比较，(n^2/4)次交换
//最坏情况(n^2/2)次比较，(n^2/2)次交换
template <class Comparable>
void insertSort(std::vector<Comparable> &A, int l, int r)
{
    for (int i = l + 1; i <= r; ++i) {
        for (int j = i; j > l; --j) {
            compSwap(A[j - 1], A[j]);
        }
    }
}

//适应性插入排序
//首先将最小的元素放在第一位，这项可以当作一个标志
//在内部循环中，因为左边的元素已经有序，因此碰到小于当前值时，停止循环
template <class Comparable>
void insertSort2(std::vector<Comparable> &A, int l, int r)
{
    for (int i = r; i > l; --i) {
        compSwap(A[i - 1], A[i]);
    }

    for (int i = l + 2; i <= r; ++i) {
        int j = i;
        Comparable v = A[j];

        while (A[j - 1] > v) {
            A[j] = A[j - 1];
            j = j - 1;
        }

        A[j] = v;
    }
}

//冒泡排序，运行时间O(n^2)，稳定性算法
//(n^2/2)次比较，(n^2/2)次交换
template <class Comparable>
void bubbleSort(std::vector<Comparable> &A, int l, int r)
{
    for (int i = l; i < r; ++i) {
        for (int j = r; j > i; --j) {
            compSwap(A[j - 1], A[j]);
        }
    }
}

//晃动排序，冒泡排序的改进
//不断地更改从左到右和从右到左的数据扫描顺序
template <class Comparable>
void cocktailBubbleSort(std::vector<Comparable> &A, int l, int r)
{
    while (l < r) {
        int t = l;

        for (int j = r; j > l; --j) {
            if (A[j - 1] > A[j]) {
                std::swap(A[j - 1], A[j]);
                t = j;//更新最后交换位置
            }
        }

        l = t;//记录最后一个交换的位置

        for (int j = l; j < r; ++j) {
            if (A[j + 1] < A[j]) {
                std::swap(A[j + 1], A[j]);
                t = j;//更新最后交换位置
            }
        }

        r = t;//记录最后一个交换的位置
    }
}

//Shell排序
template <class Comparable>
void shellSort(std::vector<Comparable> &A, int l, int r)
{
    //先求步长h的序列
    int h = 1;

    for (; h <= (r - l) / 9; h = 3 * h + 1) ;

    //依次进行步长为h的插入排序
    for (; h > 0; h = h / 3) {
        //步长为h的适应性插入排序
        for (int i = l + h; i <= r; ++i) {
            int j = i;
            Comparable v = A[j];

            //添加索引有效判断，而非将最小值放到第一位
            while (j - h >= l && A[j - h] > v) {
                A[j] = A[j - h];
                j = j - h;
            }

            A[j] = v;
        }
    }
}

//计数排序，运行时间O(n)，空间消耗O(k+1)，适用于关键字少
//只对正整数排序，例如将整数看成32位的二进制数
//对10亿个数进行排列的运行时间为O(32n)≈O(nlgn)
template <class INT_TYPE>
int _digitCountSort(const INT_TYPE &val, int d) {
    d = d-1;
    return ((val >> d) & 0x01) == 0x01 ? 1 : 0;
}

//实现为内嵌基数排序的LSD-2基数排序
template <class INT_TYPE>
void countSort(std::vector<INT_TYPE> &A, int l, int r, int d)
{
    std::vector<INT_TYPE> B = A;
    const int cnt = 2;
    std::vector<int> C(cnt+1);
    for (int k = 1; k <= d; ++k) {
        for (int i = 0; i <= cnt; ++i) {
            C[i] = 0;
        }

        for (int i = l; i <= r; ++i) {
            C[_digitCountSort(A[i], k)]++;
        }

        for (int i = 1; i <= cnt; ++i) {
            C[i] = C[i] + C[i - 1];
        }

        for (int i = r; i >= l; --i) {
            B[--C[_digitCountSort(A[i], k)]] = A[i];
        }

        for (int i = l; i <= r; ++i) {
            A[i] = B[i];
        }
    }
}

//快速排序分区划分操作
template <class Comparable>
void hoarePartition(std::vector<Comparable> &A, int l, int r, int &kl, int &kr)
{
    int i = l - 1, j = r;

    while (true) {
        while (A[++i] < A[r]);

        while (A[--j] > A[r]) {
            if (l == j) {
                break;
            }
        }

        if (i >= j) {
            break;
        }

        std::swap(A[i], A[j]);
    }

    std::swap(A[i], A[r]);
    kl = i - 1;
    kr = i + 1;
}

//快速排序，三路划分(Three-Way Partition)
template <class Comparable>
void threeWayPartition(std::vector<Comparable> &A, int l, int r, int &kl, int &kr)
{
    int i = l - 1, j = r;
    int p = l - 1, q = r;

    while (true) {
        while (A[++i] < A[r]) ;

        while (A[--j] > A[r]) {
            if (l == j) {
                break;
            }
        }

        if (i >= j) {
            break;
        }

        std::swap(A[i], A[j]);

        if (A[i] == A[r]) {
            std::swap(A[++p], A[i]);
        }

        if (A[j] == A[r]) {
            std::swap(A[--q], A[j]);
        }
    }

    std::swap(A[i], A[r]);
    j = i - 1;
    i = i + 1;

    for (int k = l; k <= p; ++k, --j) {
        std::swap(A[k], A[j]);
    }

    for (int k = r - 1; k >= q; --k, ++i) {
        std::swap(A[k], A[i]);
    }

    kl = j;
    kr = i;
}

//算法导论中，快速排序算法描述的分区划分
template <class Comparable>
void clrsPartition(std::vector<Comparable> &A, int l, int r, int &kl, int &kr)
{
    int i = l - 1;

    for (int j = l; j <= r - 1; ++j) {
        if (A[j] < A[r]) {
            i = i + 1;
            std::swap(A[i], A[j]);
        }
    }

    std::swap(A[i + 1], A[r]);
    kl = i + 1 - 1;
    kr = i + 1 + 1;
}


///////////////////////////////////////////////////////////////////
//递归实现
template <class Comparable>
void quickSort(std::vector<Comparable> &A, int l, int r,
               void (*PartitionFunction)(std::vector<Comparable> &, int, int, int &, int &) = threeWayPartition<Comparable>)
{
    if (l < r) {
        int i = 0, j = 0;
        PartitionFunction(A, l, r, i, j);
        quickSort(A, l, i, PartitionFunction);
        quickSort(A, j, r, PartitionFunction);
    }
}
///////////////////////////////////////////////////////////////////


///////////////////////////////////////////////////////////////////
//快速排序，递归实现，利用插入排序优化
template <class Comparable>
void _quickSortInsert(std::vector<Comparable> &A, int l, int r,
                      void (*PartitionFunction)(std::vector<Comparable> &, int, int, int &, int &) = threeWayPartition<Comparable>)
{
    const int M = 10;

    if (l < r) {
        if (r - l <= M) {
            return;
        }

        int i = 0, j = 0;
        PartitionFunction(A, l, r, i, j);
        _quickSortInsert(A, l, i, PartitionFunction);
        _quickSortInsert(A, j, r, PartitionFunction);
    }
}

template <class Comparable>
void quickSortInsert(std::vector<Comparable> &A, int l, int r,
                     void (*PartitionFunction)(std::vector<Comparable> &, int, int, int &, int &) = threeWayPartition<Comparable>)
{
    _quickSortInsert(A, l, r, PartitionFunction);
    insertSort2(A, l, r);
}
///////////////////////////////////////////////////////////////////


///////////////////////////////////////////////////////////////////
//快速排序优化2：利用三数取中和插入排序
template <class Comparable>
void _quickSortMedianOfThreeAndInsert(std::vector<Comparable> &A, int l, int r,
                                      void (*PartitionFunction)(std::vector<Comparable> &, int, int, int &, int &) = threeWayPartition<Comparable>)
{
    static const int M = 20;

    if (l < r) {
        if (r - l <= M) {
            return;
        }

        std::swap(A[(l + r) / 2], A[r - 1]);
        compSwap(A[l], A[r - 1]);
        compSwap(A[l], A[r]);
        compSwap(A[r - 1], A[r]);

        int i = 0, j = 0;
        PartitionFunction(A, l + 1, r - 1, i, j);
        _quickSortMedianOfThreeAndInsert(A, l + 1, i, PartitionFunction);
        _quickSortMedianOfThreeAndInsert(A, j, r - 1, PartitionFunction);
    }
}

template <class Comparable>
void quickSortMedianOfThreeAndInsert(std::vector<Comparable> &A, int l, int r,
                                     void (*PartitionFunction)(std::vector<Comparable> &, int, int, int &, int &) = threeWayPartition<Comparable>)
{
    _quickSortMedianOfThreeAndInsert(A, l, r, PartitionFunction);
    insertSort2(A, l, r);
}
///////////////////////////////////////////////////////////////////


///////////////////////////////////////////////////////////////////
//循环实现，利用stack实现
template <class Comparable>
void quickSortLoop(std::vector<Comparable> &A, int l, int r,
                   void (*PartitionFunction)(std::vector<Comparable> &, int, int, int &, int &) = threeWayPartition<Comparable>)
{
    std::stack<int> s;
    s.push(l);
    s.push(r);

    while (!s.empty()) {
        r = s.top();
        s.pop();
        l = s.top();
        s.pop();

        if (l >= r) {
            continue;
        }

        int i = 0, j = 0;
        PartitionFunction(A, l, r, i, j);

        if (i - l + 1 > r - j + 1) {
            s.push(l);
            s.push(i);
            s.push(j);
            s.push(r);
        } else {
            s.push(j);
            s.push(r);
            s.push(l);
            s.push(i);
        }
    }
}
///////////////////////////////////////////////////////////////////

///////////////////////////////////////////////////////////////////
//归并操作，稳定版本，没有去掉判断
template <class Comparable>
void mergeOrigin(std::vector<Comparable> &A, int l, int m, int r)
{
    std::vector<Comparable> B(r - l + 1);
    int i = l, j = m + 1;
    int k = l;

    while (i <= m && j <= r) {
        B[k++ -l] = (A[i] < A[j]) ? A[i++] : A[j++];
    }

    while (i <= m) {
        B[k++ -l] = A[i++];
    }

    while (j <= r) {
        B[k++ -l] = A[j++];
    }

    for (int k = l; k <= r; ++k) {
        A[k] = B[k - l];
    }
}

//归并操作，稳定版本，利用最大尾标志去掉判断
template <class Comparable>
void mergeUseMax(std::vector<Comparable> &A, int l, int m, int r)
{
    std::vector<Comparable> B, C;
    B.resize(m - l + 1 + 1);

    for (int k = l; k <= m; ++k) {
        B[k - l] = A[k];
    }

    B[m - l + 1] = std::numeric_limits<int>::max();

    C.resize(r - m + 1);

    for (int k = m + 1; k <= r; ++k) {
        C[k - (m + 1)] = A[k];
    }

    C[r - m] = std::numeric_limits<int>::max();

    int i = 0, j = 0;

    for (int k = l; k <= r; ++k) {
        A[k] = (B[i] < C[j]) ? B[i++] : C[j++];
    }
}

//归并操作，去掉判断，非稳定版
template <class Comparable>
void mergeExpand(std::vector<Comparable> &A, int l, int m, int r)
{
    std::vector<Comparable> B;
    B.resize(r - l + 1);

    for (int k = l; k <= m; ++k) {
        B[k - l] = A[k];
    }

    for (int k = r; k >= m + 1; --k) {
        B[k - l] = A[m + 1 + r - k];
    }

    int i = 0, j = r - l;

    for (int k = l; k <= r; ++k) {
        A[k] = (B[i] < B[j]) ? B[i++] : B[j--];
    }
}


///////////////////////////////////////////////////////////////////
//归并排序，自顶向下，用递归实现
//算法稳定性与归并操作的稳定性一致
template <class Comparable>
void mergeSort(std::vector<Comparable> &A, int l, int r,
               void (*MergeFunction)(std::vector<Comparable> &, int, int, int) = mergeUseMax<Comparable>)
{
    if (l < r) {
        int m = (l + r) / 2;
        mergeSort(A, l, m, MergeFunction);
        mergeSort(A, m + 1, r, MergeFunction);
        MergeFunction(A, l, m, r);
    }
}

///////////////////////////////////////////////////////////////////
//归并排序，自顶向下，用递归实现
//算法稳定性与归并操作的稳定性一致
//对于小部分数据，最后用插入排序优化
template <class Comparable>
void mergeSortWithInsert(std::vector<Comparable> &A, int l, int r,
                         void (*MergeFunction)(std::vector<Comparable> &, int, int, int) = mergeUseMax<Comparable>)
{
    static const int M = 20;

    if (l < r) {
        if (r - l + 1 <= M) {
            insertSort2(A, l, r);
            return;
        }

        int m = (l + r) / 2;
        mergeSortWithInsert(A, l, m, MergeFunction);
        mergeSortWithInsert(A, m + 1, r, MergeFunction);
        MergeFunction(A, l, m, r);
    }
}
///////////////////////////////////////////////////////////////////

///////////////////////////////////////////////////////////////////
//归并算法，自底向上，用循环实现
//算法稳定性与归并操作的稳定性一致
template <class Comparable>
void mergeSortLoop(std::vector<Comparable> &A, int l, int r,
                   void (*MergeFunction)(std::vector<Comparable> &, int, int, int) = mergeUseMax<Comparable>)
{
    for (int m = 1; m <= r - l; m = m + m) {
        for (int i = l; i <= r - m; i = i + m + m) {
            MergeFunction(A, i, i + m - 1, std::min(i + m + m - 1, r));
        }
    }
}
///////////////////////////////////////////////////////////////////


///////////////////////////////////////////////////////////////////
//归并算法，自底向上，用循环实现
//算法稳定性与归并操作的稳定性一致
//对于小部分数据，最后用插入排序优化
template <class Comparable>
void mergeSortLoopWithInsert(std::vector<Comparable> &A, int l, int r,
                             void (*MergeFunction)(std::vector<Comparable> &, int, int, int) = mergeUseMax<Comparable>)
{
    static const int M = 20;

    for (int m = 1; m <= r - l; m = m + m) {
        for (int i = l; i <= r - m; i = i + m + m) {
            if (m <= M) {
                insertSort2(A, i, std::min(i + m + m - 1, r));
            } else {
                MergeFunction(A, i, i + m - 1, std::min(i + m + m - 1, r));
            }
        }
    }
}
///////////////////////////////////////////////////////////////////


///////////////////////////////////////////////////////////////////
//归并操作，使用备份数组
template <class Comparable>
void mergeWithCopy(std::vector<Comparable> &A, std::vector<Comparable> &B, int l, int m, int r)
{
    int i = l, j = m + 1;
    int k = l;

    while (i <= m && j <= r) {
        B[k++] = (A[i] < A[j]) ? A[i++] : A[j++];
    }

    while (i <= m) {
        B[k++] = A[i++];
    }

    while (j <= r) {
        B[k++] = A[j++];
    }

    for (int i = l; i <= r; ++i) {
        A[i] = B[i];
    }
}

//归并排序
//利用备份数组减少COPY
template <class Comparable>
void _mergeSrotWithCopy(std::vector<Comparable> &A, std::vector<Comparable> &B, int l, int r)
{
    if (l < r) {
        int m = (l + r) / 2;
        _mergeSrotWithCopy(A, B, l, m);
        _mergeSrotWithCopy(A, B, m + 1, r);
        mergeWithCopy(A, B, l, m, r);
    }
}
template <class Comparable>
void mergeSortWithCopy(std::vector<Comparable> &A, int l, int r)
{
    std::vector<Comparable> B = A;
    _mergeSrotWithCopy(A, B, l, r);
}


//归并排序
//利用备份数组和插入排序
template <class Comparable>
void _mergeSrotWithCopyInsert(std::vector<Comparable> &A, std::vector<Comparable> &B, int l, int r)
{
    static const int M = 20;

    if (l < r) {
        if (r - l + 1 <= M) {
            insertSort2(A, l, r);
            return ;
        }

        int m = (l + r) / 2;
        _mergeSrotWithCopy(A, B, l, m);
        _mergeSrotWithCopy(A, B, m + 1, r);
        mergeWithCopy(A, B, l, m, r);
    }
}

template <class Comparable>
void mergeSortWithCopyInsert(std::vector<Comparable> &A, int l, int r)
{
    std::vector<Comparable> B = A;
    _mergeSrotWithCopyInsert(A, B, l, r);
}
///////////////////////////////////////////////////////////////////


///////////////////////////////////////////////////////////////////
//自底向上维持堆属性
//其中k为序号，以一为基
template <class Comparable>
void _fixUp(std::vector<Comparable> &A, int k)
{
    while (k > 1 && A[k - 1] > A[k / 2 - 1]) {
        std::swap(A[k - 1], A[k / 2 - 1]);
        k = k / 2;
    }
}

//自顶向下维持堆属性
//k,n是以一为基的序号
template <class Comparable>
void _fixDown(std::vector<Comparable> &A, int l, int k, int n)
{
    while (2 * k <= n) {
        int j = 2 * k;

        if (j < n && A[l + j - 1] < A[l + j + 1 - 1]) {
            ++j;
        }

        if (A[l + k - 1] > A[l + j - 1]) {
            break;
        }

        std::swap(A[l + k - 1], A[l + j - 1]);
        k = j;
    }
}

//堆排序
template <class Comparable>
void heapSort(std::vector<Comparable> &A, int l, int r)
{
    int n = r - l + 1;

    for (int k = n / 2; k >= 1; --k) {
        _fixDown(A, l, k, n);
    }

    while (n > 1) {
        std::swap(A[l + n - 1], A[l + 1 - 1]);
        _fixDown(A, l, l + 1, --n);
    }
}
///////////////////////////////////////////////////////////////////


///////////////////////////////////////////////////////////////////
//获得值val的第d位
template <class Comparable>
int _digitBinary(const Comparable &val, int d)
{
    return ((val >> ((int)sizeof(Comparable) * 8 - d)) & 0x01) == 0x01 ? 1 : 0;
}

//二进制快速排序，只能排序正整数，因为最高位为1时代表负值，负值应该在正数的前面
template <class Comparable>
void _quickSortUseBinary(std::vector<Comparable> &A, int l, int r, int d)
{
    if (l >= r || d > (int)sizeof(Comparable) * 8) {
        return;
    }

    int i = l, j = r;

    while (i != j) {
        while (_digitBinary(A[i], d) == 0 && i < j) {
            ++i;
        }

        while (_digitBinary(A[j], d) == 1 && j > i) {
            --j;
        }

        std::swap(A[i], A[j]);
    }

    if (_digitBinary(A[r], d) == 0) {
        ++i;
    }

    _quickSortUseBinary(A, l, i - 1, d + 1);
    _quickSortUseBinary(A, i, r, d + 1);
}

template <class Comparable>
void quickSortUseBinary(std::vector<Comparable> &A, int l, int r)
{
    _quickSortUseBinary(A, l, r, 1);
}
///////////////////////////////////////////////////////////////////


///////////////////////////////////////////////////////////////////
//最高优先位排序
template <class Comparable>
int _digitDecimal(const Comparable &val, int d)
{
    int tmp = val;

    for (int i = d; i > 1; --i) {
        tmp = tmp / 10;
    }

    return tmp % 10;
}

template <class Comparable>
void _mostSignificantDigitSort(std::vector<Comparable> &A, std::vector<Comparable> &B, int l, int r, int d)
{
    if (l >= r || d < 1) {
        return ;
    }

    static const int M = 20;

    if (r - l + 1 <= M) {
        insertSort2(A, l, r);
        return ;
    }

    //关键字为0、1、2、3、4、5、6、7、8、9
    //但是最后的分区为[0,1)[1,2)[2,3)[3,4)[4,5)[5,6)[6,7)[7,8)[8,9)[9,x)
    //所以需要11个数字，非常关键
    static const int R = 11;
    std::vector<Comparable> count(R);

    for (int i = 0; i < R; ++i) {
        count[i] = 0;
    }

    for (int i = l; i <= r; ++i) {
        count[_digitDecimal(A[i], d)]++;
    }

    for (int i = 1; i < R; ++i) {
        count[i] += count[i - 1];
    }

    for (int i = r; i >= l; --i) {
        B[l - 1 + count[_digitDecimal(A[i], d)]--] = A[i];
    }

    for (int i = l; i <= r; ++i) {
        A[i] = B[i];
    }

    //根据分区，进行快速排序
    _mostSignificantDigitSort(A, B, l, l + count[0] - 1, d - 1);

    for (int i = 0; i < R - 1; ++i) {
        _mostSignificantDigitSort(A, B, l + count[i], l + count[i + 1] - 1, d - 1);
    }
}

//MSD-10基数排序，结合计数排序和快速排序
//整体框架为快速排序，利用计数排序进行分区
template <class Comparable>
void mostSignificantDigitSort(std::vector<Comparable> &A, int l, int r)
{
    std::vector<Comparable> B = A;
    _mostSignificantDigitSort(A, B, l, r, 20);
}
///////////////////////////////////////////////////////////////////


///////////////////////////////////////////////////////////////////
int _char(const std::string &s, int d)
{
    if (1 <= d && d <= (int)s.length()) {
        int tmp = s.at(d - 1);

        if (97 <= tmp && tmp <= 122) {
            return tmp - 32;
        } else if (65 <= tmp && tmp <= 90) {
            return tmp + 32;
        } else {
            return tmp;
        }
    } else {
        return 0;
    }
}
//三路MSD排序，仅对字符串进行排序
void _threeWayMsdSort(std::vector<std::string> &A, int l, int r, int d)
{
    if (l >= r || d > 256) {
        return ;
    }

    //static const int M = 20;
    //对于小规模数据，利用插入排序进行优化
    //if (r-l+1 <= M) {insertSort2(A, l, r); return;}
    //利用三数取中选择中间值
    int m = (l + r) / 2;

    if (_char(A[l], d) > _char(A[m], d)) {
        std::swap(A[l], A[m]);
    }

    if (_char(A[l], d) > _char(A[r], d)) {
        std::swap(A[l], A[r]);
    }

    if (_char(A[m], d) > _char(A[r], d)) {
        std::swap(A[m], A[r]);
    }

    //利用三路划分进行分区
    int i = l - 1, j = r;
    int p = l - 1, q = r;
    int v = _char(A[r], d);

    while (i < j) {
        while (_char(A[++i], d) < _char(A[r], d));

        while (_char(A[--j], d) > _char(A[r], d));

        if (i >= j) {
            break;
        }

        std::swap(A[i], A[j]);

        if (_char(A[i], d) == v) {
            std::swap(A[i], A[++p]);
        }

        if (_char(A[j], d) == v) {
            std::swap(A[j], A[--q]);
        }
    }

    for (int k = l; k <= p; ++k) {
        std::swap(A[k], A[j--]);
    }

    for (int k = r; k >= q; --k) {
        std::swap(A[k], A[i++]);
    }

    _threeWayMsdSort(A, l, j, d);

    if (v != 0) {
        _threeWayMsdSort(A, j + 1, i - 1, d + 1);
    }

    _threeWayMsdSort(A, i, r, d);
}

void threeWayMsdSort(std::vector<std::string> &A, int l, int r)
{
    _threeWayMsdSort(A, l, r, 1);
}
///////////////////////////////////////////////////////////////////


///////////////////////////////////////////////////////////////////
//LSD基数排序
int _charLsd(const std::string &s, int k)
{
    int d = s.length() - k;

    if (1 <= d && d <= (int)s.length()) {
        int tmp = s.at(d - 1);

        if (97 <= tmp && tmp <= 122) {
            return tmp - 97 + 1;
        } else if (65 <= tmp && tmp <= 90) {
            return tmp - 65 + 27;
        } else {
            return 0;
        }
    } else {
        return 0;
    }
}

//LSD基数排序
//对所有长度相等的字符串进行排序
//从左向右利用计数排序进行扫描
//计数排序是稳定算法
void radixLsdSort(std::vector<std::string> &A, int l, int r, int len)
{
    std::vector<std::string> B = A;
    const int cnt = 2 * 26 + 1;
    std::vector<int> C(cnt + 1);

    for (int d = 1; d <= len; ++d) {
        for (int i = 0; i <= cnt; ++i) {
            C[i] = 0;
        }

        for (int i = l; i <= r; ++i) {
            C[_charLsd(A[i], d)]++;
        }

        for (int i = 1; i <= cnt; ++i) {
            C[i] += C[i - 1];
        }

        for (int i = r; i >= l; --i) {
            //数组是以0为基，所以先自减
            //如果数组是以1为基，应该后自减
            B[--C[_charLsd(A[i], d)]] = A[i];
        }

        for (int i = l; i <= r; ++i) {
            A[i] = B[i];
        }
    }
}
#endif
